#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

int
kmp(const char *word, const char *text)
{
    int i, j, count;
    int word_len, text_len;
    int *next;

    word_len = strlen (word);
    text_len = strlen (text);

    next = (int*) malloc (sizeof(int)*(word_len + 1));
    next[0] = j = -1;
    for (i = 1; i < word_len; ++i) {
        while (j >= 0 && word[j + 1] != word[i])
            j = next[j];
        if (word[i] == word[j + 1])
            ++j;
        next[i] = j;
    }

    for (count = i = 0, j = -1; i < text_len; ++i) {
        while (j >= 0 && text[i] != word[j + 1])
            j = next[j];
        if (text[i] == word[j + 1]) {
            if (++j == word_len -1) {
                ++count;
                j = next[j];
            }
        }
    }
    return count;
}

int
main(int argc, char *argv[])
{
    int n, ans;
    int left, right, mid;
    string str, ts;

    cin >> n;
    while (n--) {
        cin >> str;

        ans = 0;
        left = 1, right = str.size() / 3;
        while (left <= right) {
            mid = (left + right) >> 1;
            ts = str.substr(0, mid);

            if (ts != str.substr(str.size() - mid)) {
                right = mid - 1;
            } else if (kmp(ts.c_str(), str.substr(mid, str.size() - 2 *mid).c_str()) > 0) {
                left = mid + 1;
                ans = mid;
            } else {
                right = mid - 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
